package leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-12 01:24
 **/
public class LeetCode334 {

    //贪心
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }

    //双向遍历
    /*public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        //数组长度小于3不可能有满足条件的三元子序列
        if (n < 3) {
            return false;
        }

        //维护左边最小值
        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }

        //维护右边最大值
        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(nums[i], rightMax[i + 1]);
        }

        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i] && nums[i] < rightMax[i]) {
                return  true;
            }
        }
        return false;
    }*/

}
